#pragma once
#include <memory>
template <class T>
class StackNode_
{
public:
    T data;
    StackNode_ *prev;
};
template <class T, class Alloc = std::allocator<T>>
class StackAlloc
{
public:
    typedef StackNode_<T> Node;
    typedef typename Alloc::template rebind<Node>::other allocator;

    StackAlloc() { head_ = nullptr; }
    ~StackAlloc() { clear(); }
    bool empty() { return !head_; }
    void clear();
    void push(T element);
    void pop();
    T top() { return head_->data; }

private:
    Node *head_;
    allocator allocator_;
};
template <class T, class Alloc>
void StackAlloc<T, Alloc>::clear()
{
    Node *cur = head_;
    while (cur)
    {
        Node *tmp = cur->prev;
        allocator_.destroy(cur);
        allocator_.deallocate(cur, 1);
        cur = tmp;
    }
    head_ = nullptr;
}
template <class T, class Alloc>
void StackAlloc<T, Alloc>::push(T element)
{
    Node *ins = allocator_.allocate(1);
    allocator_.construct(ins, Node());
    ins->data = element;
    ins->prev = head_;
    head_ = ins;
}
template <class T, class Alloc>
void StackAlloc<T, Alloc>::pop()
{
    Node *res = head_->prev;
    allocator_.destroy(head_);
    allocator_.deallocate(head_, 1);
    head_ = res;
}
